Na teoria da complexidade computacional, a Pesquisa Local Polinomial (PLS) é uma classe de complexidade que modela a dificuldade de encontrar uma solução ótima localmente para um problema de otimização.

Um problema PLS ${\displaystyle L}$ tem um conjunto ${\displaystyle D_{L}}$ de instâncias que são codificados usando seqüências de caracteres sobre um alfabeto finito ${\displaystyle \Sigma }$. Para cada instância ${\displaystyle x}$ existe uma solução finita de ${\displaystyle F_{L}(x)}$. Cada solução ${\displaystyle s\in F_{L}(x)}$ tem um número inteiro não-negativo de custo dado por uma função ${\displaystyle c_{L}(s,x)}$ e uma vizinhança ${\displaystyle N(s,x)\subseteq F_{L}(x)}$. Além disso, a existência dos três seguintes algoritmos de tempo polinomial é necessária:

• Algoritmo ${\displaystyle A_{L}}$ produz alguma solução ${\displaystyle A_{L}(x)\in F_{L}(x)}$.
• Algoritmo ${\displaystyle B_{L}}$ determina o valor de ${\displaystyle c_{L}(s,x)}$.
• Algoritmo ${\displaystyle C_{L}}$ mapeia um solução ${\displaystyle s\in F_{L}(x)}$ para um elemento ${\displaystyle s'\in N(s,x)}$ de tal forma que ${\displaystyle c_{L}(s',x)<c_{L}(s,x)}$ se tal elemento não existe. Caso contrário, ${\displaystyle C_{L}}$ relata que tal elemento não existe.

Uma instância ${\displaystyle D_{L}}$ tem a estrutura de um grafo implícito, os vértices sendo as soluções com duas soluções ${\displaystyle s,s'\in F_{L}(x)}$ conectados por um arco direcionado se e somente se ${\displaystyle s'\in N(s,x)}$. O mais interessante problema computacional é o seguinte:

Dado alguma instância ${\displaystyle x}$ de um problema PLS ${\displaystyle L}$, encontrar um local optimum de ${\displaystyle c_{L}(s,x)}$, i.e. uma solução ${\displaystyle s\in F_{L}(x)}$ tal que ${\displaystyle c_{L}(s',x)\geq c_{L}(s,x)}$ para todos ${\displaystyle s'\in N(s,x)}$

O problema pode ser resolvido usando o seguinte algoritmo:

1. Use ${\displaystyle A_{L}}$ para encontrar uma solução inicial ${\displaystyle s}$
2. Use o algoritmo ${\displaystyle C_{L}}$ para encontrar uma solução melhor ${\displaystyle s'\in N(s,x)}$. Se tal solução existe, substituir ${\displaystyle s}$ por ${\displaystyle s'}$, caso contrário retorne ${\displaystyle s}$

Infelizmente, isso geralmente leva um número exponencial de passos de melhoria para encontrar um local optimum, mesmo se o problema ${\displaystyle L}$ pode ser resolvido exatamente em tempo polinomial.

Exemplos de problemas PLS-completo incluem relativos ao local optimum do problema do caixeiro viajante, corte máximo e satisfatibilidade, bem como a procura de um puro equilíbrio de Nash de um jogo congestionamento.

PLS é uma subclasse da TFNP, uma classe de complexidade estreitamente relacionada com a NP que descreve problemas computacionais em que é garantida a existência de uma solução e que pode ser reconhecida em tempo polinomial. Por um problema no PLS, é garantida a existência de uma solução porque o vértice de custo mínimo do gráfico inteiro é uma solução válida, e a validade de uma solução pode ser verificada através do cálculo de seus vizinhos e comparando os custos de cada um.